/**
 * 队列先进先出
 *
 * @alias Queue
 * @constructor
 */
export class Queue<T> {
  private items: T[]
  private frontIndex: number
  private backIndex: number

  constructor() {
    this.items = []
    this.frontIndex = 0
    this.backIndex = 0
  }

  /**
   * Adds an item to the back of the queue
   * @param item The item to be added
   */
  enqueue(item: T): void {
    this.items[this.backIndex] = item
    this.backIndex++
  }

  contains(t: T): number {
    if (this.isEmpty()) {
      return -1
    }
    for (let i = this.frontIndex; i < this.backIndex; i++) {
      if (this.items[i] === t) {
        return i
      }
    }
    return -1
  }
  /**
   * Removes and returns the item at the front of the queue
   * @returns The front item or undefined if queue is empty
   */
  dequeue(): T | undefined {
    if (this.isEmpty()) {
      return undefined
    }
    const item = this.items[this.frontIndex]
    delete this.items[this.frontIndex]
    this.frontIndex++
    return item
  }

  /**
   * Returns the item at the front of the queue without removing it
   * @returns The front item or undefined if queue is empty
   */
  peek(): T | undefined {
    if (this.isEmpty()) {
      return undefined
    }
    return this.items[this.frontIndex]
  }

  /**
   * Checks if the queue is empty
   * @returns true if queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.frontIndex === this.backIndex
  }

  /**
   * Gets the current size of the queue
   * @returns The number of items in the queue
   */
  size(): number {
    return this.backIndex - this.frontIndex
  }

  get length(): number {
    return this.backIndex - this.frontIndex
  }

  /**
   * Clears all items from the queue
   */
  clear(): void {
    this.items = []
    this.frontIndex = 0
    this.backIndex = 0
  }

  /**
   * Returns a string representation of the queue
   * @returns The queue as a string
   */
  toString(): string {
    if (this.isEmpty()) {
      return 'Queue []'
    }
    return `Queue [${this.items.slice(this.frontIndex, this.backIndex).join(', ')}]`
  }
}

export class CircularQueue<T> {
  private items: (T | undefined)[]
  private capacity: number
  private frontIndex: number
  private backIndex: number
  private count: number

  constructor(capacity: number = 100) {
    this.items = new Array(capacity)
    this.capacity = capacity
    this.frontIndex = 0
    this.backIndex = 0
    this.count = 0
  }

  enqueue(item: T): void {
    if (this.isFull()) {
      this.resize()
    }

    this.items[this.backIndex] = item
    this.backIndex = (this.backIndex + 1) % this.capacity
    this.count++
  }

  dequeue(): T | undefined {
    if (this.isEmpty()) {
      return undefined
    }
    const item = this.items[this.frontIndex]
    this.items[this.frontIndex] = undefined
    this.frontIndex = (this.frontIndex + 1) % this.capacity
    this.count--
    return item
  }

  peek(): T | undefined {
    if (this.isEmpty()) {
      return undefined
    }
    return this.items[this.frontIndex]
  }

  isEmpty(): boolean {
    return this.count === 0
  }

  isFull(): boolean {
    return this.count === this.capacity
  }

  size(): number {
    return this.count
  }

  get length(): number {
    return this.count
  }

  contains(t: T): number {
    if (this.isEmpty()) {
      return -1
    }
    for (let i = this.frontIndex; i < this.backIndex; i++) {
      if (this.items[i] === t) {
        return i
      }
    }
    return -1
  }

  clear(): void {
    this.items = new Array(this.capacity)
    this.frontIndex = 0
    this.backIndex = 0
    this.count = 0
  }

  private resize(): void {
    const newCapacity = this.capacity * 2
    const newItems = new Array(newCapacity)

    for (let i = 0; i < this.count; i++) {
      newItems[i] = this.items[(this.frontIndex + i) % this.capacity]
    }

    this.items = newItems
    this.frontIndex = 0
    this.backIndex = this.count
    this.capacity = newCapacity
  }
}
